package pers.sloera.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * 使数组和能被 P 整除
 *
 * @author sloera
 * @date 2023-03-10 21:07:38
 */
class MakeSumDivisibleByP {
    public static void main(String[] args) {
        Solution solution = new MakeSumDivisibleByP().new Solution();
        System.out.println(solution.minSubarray(new int[]{3, 1, 4, 2}, 6));
        System.out.println(solution.minSubarray(new int[]{6, 3, 5, 2}, 9));
        System.out.println(solution.minSubarray(new int[]{1, 2, 3}, 7));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minSubarray(int[] nums, int p) {
            long[] prefixSum = new long[nums.length + 1];
            // 因为删除只能删除连续的子数组，所以可以使用前缀和计算删除的子数组和
            for (int i = 0; i < nums.length; i++) {
                prefixSum[i + 1] = prefixSum[i] + nums[i];
            }
            // 什么也不去除
            long sum = prefixSum[nums.length];
            long mod = sum % p;
            if (mod == 0) {
                return 0;
            }
            // 余数相同定理 如果 (y-z) mod p = x，则 z mod p = (y-x) mod p
            // 如果 (y-z) mod p = 0，则 y mod p = z mod p
            // x为余数则：(prefixSum[j]-prefixSum[i]) mod p = x。不包括 num[j]，prefixSum的长度比num多1，所以可以遍历完
            // (prefixSum[j] - x) mod p = prefixSum[i] mod p ，  此时的i和j是满足的一对
            int min = nums.length + 1;
            Map<Long, Integer> hashMap = new HashMap<>(nums.length);
            for (int i = 0; i < prefixSum.length; i++) {
                // (prefixSum[j] - x) mod p
                // 为了避免余数为负，+p后再取余
                long lastKey = (prefixSum[i] - mod + p) % p;
                if (hashMap.containsKey(lastKey)) {
                    min = Math.min(min, i - hashMap.get(lastKey));
                }
                hashMap.put(prefixSum[i] % p, i);
            }
            // 当 min 为nums.length时，说明全部去除了，这是不被允许的。
            // 当 min 为nums.length-1时，说明没有找到合适的
            return min >= nums.length ? -1 : min;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
